package com.lwt.codetop.arrayOrSort;

// 31. 下一个排列

import java.util.Collections;

/**
 * 思路：字典序思想
 */
public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = {2, 3, 5, 4, 1};
        nextPermutation(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }

    }

    /**
     * 求某一个序列的下一个排列：字典序比它大的最小的排列
     * @param nums
     */
    private static void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
        //1. 找到第一个非降序的位置 ---> 从后往前遍历就是非严格升序的
        while(k > 0 && nums[k - 1] >= nums[k]) k -= 1;
        if(k == 0){
            // 说明当前序列已经是最大的字典序，进行反转 3 2 1 --> 1 2 3
            reverse(nums, 0, n - 1);
        }else {
            //2. 找到该位置后面的第一个比它大的最小的数，然后进行交换
            //    （这里就是为什么要逆序遍历的原因，因为非严格升序，比它大的最小的数一定在最后面）
            //     2 3 5 4 1  k - 1上才是该数（3）
            int t = k;
            while (t < n && nums[t] > nums[k - 1]) t += 1; // 找到大于3的最小的数
            swap(nums, k - 1, t - 1); // 交换
            //3. 将该位置后面的所有数进行逆序排序
            reverse(nums, k, n - 1);
        }
    }
    private static void reverse(int[] nums, int i, int j){
        while (i < j){
            swap(nums, i, j);
            i += 1;
            j -= 1;
        }
    }
    private static void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
